package subjectlist;


import com.sun.media.sound.RIFFInvalidDataException;
import com.sun.xml.internal.bind.v2.model.core.EnumLeafInfo;

import java.util.HashSet;
import java.util.Iterator;

/**
 * 题目描述：
 * 数字1～1000放在含有1001个元素的数组中，其中只有唯一的一个元素值重复，其他数字均只出现一次。
 * 设计一个算法，将重复元素找出来，要求每个数组元素只能访问一次。
 * 如果不使用辅助存储空间，能否设计一个算法实现？
 */
public class A如何找出数组中唯一的重复元素 {

    /**
     * 采用以上累加求和的方法，虽然能够解决本题的问题，但也存在一个潜在的风险，
     * 就是当数组中的元素值太大或者数组太长时，计算的和值有可能会出现溢出的情况，
     * 进而无法求解出数组中的唯一重复元素。鉴于求和法存在的局限性，可以采用位运算中异或的方法。
     * 根据异或运算的性质可知，当相同元素异或时，其运算结果为0；当相异元素异或时，其运算结果为非0；
     * 任何数与数字0进行异或运算，其运算结果为该数。本题中，正好可以使用到此方法，即将数组里的元素逐一进行异或运算，
     * 得到的值再与数字1、2、3、…、N进行异或运算，得到的最终结果即为所求的重复元素。以数组{1, 3, 4, 2, 5, 3}为例。
     * （1^3^4^2^5^3）^（1^2^3^4^5）=（1^1）^（2^2）^（3^3^3）^（4^4）^（5^5）=0^0^3^0^0=3
     */

    public static int findDup(int[]array){
        if (null == array) {
            return -1;
        }
        int len=array.length;
        int result=0;
        int i;
        for ( i = 0; i < len; i++) {
            result^=array[i];
        }
        for ( i = 0; i <len; i++) {
            result^=i;
        }
        return result;
    }

    public static void main(String[] args) {
        int []arr=new int[]{1,3,4,2,5,3};
        System.out.println(findDup(arr));
    }

    private static class B数据映射方法{

        /**
         * 因为每个数在数组中都有自己的位置，如果一个数是在自己应该在的位置（在本题中就是它的值就是它的下标，即所在的位置），
         * 那永远不会对它进行调换，也就是不会访问到它，除非它就是那个多出的数，
         * 那与它相同的数访问到它的时候便就是结果了；如果一个数所在的位置不是它应该待的地方，那它会去找它应该在的位置，
         * 在它位置的数也应该去找它应该在的位置，碰到了负数，也就是说已经出现了这个数，所以就得出结果了
         * @param array
         * @return
         */
        public static int findDup(int []array){
            if (null == array) {
                return -1;
            }
            int len=array.length;
            int index=0;
            int i=0;
            while (true) {
                //数组中的元素的值只能小于len，否则会越界
                if (array[i] >= len) {
                    return -1;
                }
                if (array[index] < 0) {
                    break;
                }
                //访问过，通过变相反数的方法进行标记
                array[index]*=-1;
                //index的后缀为array[index]
                index=-1*array[index];
                if(index>=len){
                    System.out.println("数组中有非法数字");
                    return -1;
                }
            }
            return index;
        }
    }


    /**
     * 就是采用类似于单链表是否存在环的方法进行问题求解。
     * “判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时每个元素值作为next指针指向下一个元素。
     * 本题可以转化为“已知一个单链表中存在环，找出环的入口点”这种想法。具体思路：将array[i]看作第i个元素的索引，
     * 即array[i]-＞ array[array[i]]-＞ array[array[array[i]]]-＞array[array[array[array[i]]]]-＞….最终形成一个单链表，
     * 由于数组a中存在重复元素，则一定存在一个环，且环的入口元素即为重复元素。该题的关键在于，数组array的大小是n，而元素的范围是[1,n-1]，
     * 所以array[0]不会指向自己，进而不会陷入错误的自循环。如果元素的范围中包含0，则该题不可直接采用该方法。以数组序列{1, 3, 4, 2, 5, 3}为例。
     * 按照上述规则，这个数组序列对应的单链表如下图所示。[插图]从上图可以看出这个链表有环，且环的入口点为3，所以，这个数组中重复元素为3。
     * 在实现时可以参考求单链表环的入口点的算法：用两个速度不同的变量slow和fast来访问，
     * 其中slow每次前进一步，fast每次前进两步。在有环结构中，它们总会相遇。
     * 接着从数组首元素与相遇点开始分别遍历，每次各走一步，它们必定相遇，且相遇第一点为环入口点。
     */
    private static class C环形相遇法{
        public static HashSet<Integer> findDup(int[] array,int num){
            HashSet<Integer> s=new HashSet();
            if(null==array){
                return s;
            }
            int len=array.length;
            int index=array[0];
            num=num-1;
            while (true){
                if (array[index] < 0) {
                    num--;
                    array[index]=len- num;
                    s.add(index);
                }
                if (num == 0) {
                    return s;
                }
                array[index]*=-1;
                index=array[index]*(-1);
            }
        }

        public static void main(String[] args) {
            int array[]={1,2,3,3,3,4,5,5,5,5,6};
            int num=6;
            HashSet<Integer> s= findDup(array,num);
            Iterator<Integer> iterator = s.iterator();
            while (iterator.hasNext()) {
                System.out.print(iterator.next()+" ");
            }
        }
    }
}
